
#ifndef Velyn_Subdivide_h
#define Velyn_Subdivide_h

#include <map>
#include <algorithm>

#include "Types.h"
#include "Vector.h"
#include "TMesh.h"

namespace Velyn {
    
    namespace Subdivisions {

        class Subdivide {
            
        private:
            
            // map midpoints to existing vertices in the mesh
            map<int, VertexIndex> midpointIndices;
            
            // calculates the midpoints
            Vertex calculateMidpoint(Vertex vertex0, Vertex vertex1) {
                return (vertex0 + vertex1) * 0.5;
            }
            
            Texture calculateMidpoint(Texture texture0, Texture texture1) {
                return (texture0 + texture1) * 0.5;
            }
            
            /*
             
             Calculate Normal Equation:
             
             The normal, N, would be:
                P = n1 x n2 / || n1 x n2 ||
                N = v x P
             Where
                v = v2-v1 / ||v2-v1||
             And
             V1 is the vertex position of an end point with normal n1, 
             and v2 is the other end point with normal n2. If n1 = n2, then let:
             P = n1 x v / || n1 x v ||
             And N as above.
             
             v = v2 - v1 / || v2 - v1 ||
             
             if n1 == n2 then 
                P = n1 x v / || n1 x v ||
             else
                P = n1 x n2 / || n1 x n2 ||	
             
             N = v x P 
             
             */
            
            // FIXME: interpolate this with interpolate math utility class (create the class)
            Normal calculateNormal(Vertex vertex0, Vertex vertex1, Normal normal0, Normal normal1) {
                Normal result;
                Vector3 v, p;
                
                v = vertex1 - vertex0;
                
                if(Vector3::Equals(normal0, normal1, 0.0001f)) {
                    p = normal0.cross(v);
                } else {
                    p = normal0.cross(normal1);
                }
                
                p.normalize();
                
                result = v.cross(p);
                result.normalize();
                
                // if(normal0.dot(result) > 0) {
                //    result = -result;
                // }
                
                return result;
            }
            
            // hash the vertex indicies
            int getHashKey(int point0, int point1, int hashMultiplier) {
                int key;
                
                if(point0 < point1) {
                    key = hashMultiplier * point0 + point1;
                } else {
                    key = hashMultiplier * point1 + point0;
                }
                
                return key;
            }

        public:
            
            Subdivide() {}
            
            ~Subdivide() {}
            
            
            /*
             
             Subdivide Surface:
             
             Takes one triangle and finds the midpoint for along each edge 
             and creates four triangles for each triangle in the mesh. 
             
             
                                    v0
                                    /\            
                                   /  \
                                  /    \
                                 /      \
                                /        \
                               /__________\
                             v2            v1 
             
                             becomes
             
                                    v0
                                    /\            
                                   /  \
                                  /    \
                             mp2 /\````/\ mp0
                                /  \  /  \
                               /____\/____\
                             v2     mp1    v1
             
             
             */
            
            
            TriangleMesh* subdivideSurface(TriangleMesh* mesh) {
                
                // copy over the vertices, normals, and textures
                TriangleMesh* newMesh = new TriangleMesh(*mesh);
                
                // clear the map
                midpointIndices.clear();
                
                // for each triangle
                for(int triangle = 0; triangle < mesh->numberTriangles(); triangle++) {
                    
                    // get the vertices for the triangle
                    VertexList vertices = mesh->getVertices(triangle);
                    
                    // get the indicies of the vertex indices for the triangle
                    VertexIndexList vertexIndex = mesh->getVertexIndices(triangle);
                    
                    // get the normals for the triangle
                    NormalList normals = mesh->getNormals(triangle);
                    
                    // get the textures
                    TextureList textures = mesh->getTextures(triangle);
                    
                    int hashKey;
                    int midpointIndex[3];
                    
                    // NormalList normals = mesh->calculateNormals(triangle);
                    
                    map<int, int>::const_iterator findIterator;
                    
                    // hash the set of vertices and see if they exist in the map
                    // if they do then use the index in the map
                    // if they do not exist then create the midpoint and map it to that index
                    
                    // for midpoint 1
                    // get the hash key
                    hashKey = getHashKey(vertexIndex[0], vertexIndex[1], mesh->numberVertices());
                    
                    // check if it is in the map
                    findIterator = midpointIndices.find(hashKey);
                    
                    // if the key does not exist
                    if(findIterator == midpointIndices.end()) {
                        Vertex midpoint;
                        Normal normal;
                        Texture texture;
                        
                        // create the midpoint
                        midpoint = calculateMidpoint(vertices[0], vertices[1]);
                        
                        // add the midpoint to the vertex record of the newMesh
                        midpointIndex[0] = newMesh->addVertex(midpoint);
                        
                        // calculate the normals
                        normal = calculateNormal(vertices[0], vertices[1], normals[0], normals[1]);
                        
                        // add the new normal
                        newMesh->addNormal(normal);
                        
                        // calculate the texture
                        texture = calculateMidpoint(textures[0], textures[1]);
                        
                        // add the new texture
                        newMesh->addTexture(texture);
                        
                        // and map its hash key to its index in the vertex record
                        midpointIndices[hashKey] = midpointIndex[0];
                    } else {
                        
                        // if the key does exist, get its index from the map
                        midpointIndex[0] = findIterator->second;
                    }
                    
                    // repeat for midpoint 2
                    hashKey = getHashKey(vertexIndex[1], vertexIndex[2], mesh->numberVertices());
                    findIterator = midpointIndices.find(hashKey);
                    
                    if(findIterator == midpointIndices.end()) {
                        Vertex midpoint;
                        Normal normal;
                        Texture texture;
                        
                        midpoint = calculateMidpoint(vertices[1], vertices[2]);
                        midpointIndex[1] = newMesh->addVertex(midpoint);
                        
                        normal = calculateNormal(vertices[1], vertices[2], normals[1], normals[2]);
                        newMesh->addNormal(normal);
                        
                        texture = calculateMidpoint(textures[1], textures[2]);
                        newMesh->addTexture(texture);
                        
                        midpointIndices[hashKey] = midpointIndex[1];
                    } else  {
                        midpointIndex[1] = findIterator->second;
                    }
                    
                    // and for midpoint 3
                    hashKey = getHashKey(vertexIndex[2], vertexIndex[0], mesh->numberVertices());
                    findIterator = midpointIndices.find(hashKey);
                    
                    if(findIterator == midpointIndices.end()) {
                        Vertex midpoint;
                        Normal normal;
                        Texture texture;
                        
                        midpoint = calculateMidpoint(vertices[2], vertices[0]);
                        midpointIndex[2] = newMesh->addVertex(midpoint);
                        
                        normal = calculateNormal(vertices[0], vertices[2], normals[0], normals[2]);
                        newMesh->addNormal(normal);
                        
                        texture = calculateMidpoint(textures[2], textures[0]);
                        newMesh->addTexture(texture);
                        
                        midpointIndices[hashKey] = midpointIndex[2];
                    } else {
                        midpointIndex[2] = findIterator->second;
                    }
                    
                    // add triangles to newMesh in clockwise order
                    newMesh->addTriangle(vertexIndex[0], midpointIndex[0], midpointIndex[2]);
                    newMesh->addTriangle(midpointIndex[0], vertexIndex[1], midpointIndex[1]);
                    newMesh->addTriangle(midpointIndex[0], midpointIndex[1], midpointIndex[2]);
                    newMesh->addTriangle(midpointIndex[2], midpointIndex[1], vertexIndex[2]);
                }
                
                // swap the addresses of mesh and newMesh
                // std::swap(mesh, newMesh);
            
                delete mesh;
                    
                return newMesh;
        
            }
        
        };
            
    }

}

#endif
